

\section{编程问题总结}

本章包含了一些算法题目，几乎所有题目都可以用枚举的方法低效地完成，记作方法零。遇到题目，可以依次尝试枚举、分治和动态规划。

\subsection{空间节省技术}
\ref{problem:sparseMatrix}给出了稀疏矩阵存储方式。对于其他空间节省技术，经常是通过仅存储差量来实现,如\cite{pp}10.6.4,10.6.5。

\subsection{循环不变式}
二分搜索：待搜索值在l\dots u之间的区间中。
堆siftup：heap(1,n) except perhaps between i and its parent。
堆siftdown：heap(1,n) except perhaps between i and its (0,1,2)children
快速排序partition：
子数组最大和：
BST搜索：

\subsection{利用哨兵减少判断}
哨兵有两个意思\cite{wikipedia}，一是结构化表示结尾的最末特殊值(字符串，文件，链表)，二是用于消除末尾判断的特殊值。本节取第二个意思。

求最值:\cite{pp}9.5.8利用哨兵元素找出数组最大值，x[n]时刻保存当前最大值。 需要在末尾多分配一个元素对空间，即可访问x[n]。同时，如果在开头额外分配元素，则可访问x[-1]。

二分搜索:\cite{pp}9.3修改二分搜索算法，将x[-1]和x[n]看作假想的哨兵值(参\ref{codes:binsort})。

顺序搜索:\cite{pp}9.2问题3将哨兵值用在了顺序顺序搜索中，x[n]保存待搜索值。

有序链表和BST插入:参\ref{problem:listInsert}和\ref{problem:BSTInsert}。

堆siftup:首元素作哨兵，取极小值。

快速排序Partition:

\subsection{克服malloc瓶颈}
\cite{pp}9.1,9.5.2,13.6.5。如果需要分配多个相同大小的结点，可以一次性malloc来节省时间，自行管理空间。

\subsection{if-else灾难与switch膨胀}
转为为搜索问题(\cite{pp}3.7.1)，或利用多态(\cite{refractor})。

\subsection{分治法时间复杂度}
\begin{displaymath}
    T(n)=aT(n/b)+f(n)
\end{displaymath}

\begin{math}
    \textrm{其中} a \ge 1, b > 1, f(n) \textrm{is asymptotically positive}。
\end{math}

三种常见情况：
\begin{enumerate}
    \item 
\begin{displaymath}
    f(n)=O(n^{log_{b}a-\epsilon}), \epsilon>0, \textrm{则 }T(n)=\Theta(n^{log_{b}a})
\end{displaymath}

    \item 
\begin{displaymath}
    f(n)=O(n^{log_{b}a}lg^{k}n), \textrm{则 }T(n)=\Theta(n^{log_{b}a}lg^{k+1}n)
\end{displaymath}

    \item 
\begin{displaymath}
    f(n)=O(n^{log_{b}a+\epsilon}), \epsilon>0, \textrm{则}T(n)=\Theta(f(n))
\end{displaymath}

\end{enumerate}

\label{divide_complex}


\section{历法常识}

\subsection{闰年的计算}
\label{subsec:leapyear}
闰年(leap year)规则为： 西元年份逢4的倍数闰、100的倍数不闰、400的倍数闰。例如：公元1992、1996 年等为4的倍数，故为闰年；公元1800、1900、2100年为100的倍数，当年不闰；公元1600、2000、2400年为400的倍数，有闰。其他年份为平年(common year)。公元前之闰年出现在1, 5, 9, 13, 因此无法以“除以4”计算。公元元年为公元1年，没有零年。有人提议4000的倍数不闰，未被采纳。


\subsection{阳历和阴历}
阳历（又称太阳历，英语：Solar Calendar），为据地球围绕太阳公转轨道位置，或地球上所呈现出太阳直射点的周期性变化，所制定的历法。在华语文化中，“阳历”一词有时会被泛指为公历，以与传统的农历有所区别。

阴历（英语：lunar calendar）又称太阴历，在天文学中与阳历对应，指主要按月亮的月相周期来安排的历法。它的一年有12个朔望月，约354或355日。主要根据月亮绕地球运行一周时间为一个月（29.5306天），大月30日，小月29日。纯粹的阴历有希腊历和伊斯兰历，而大部分通常说的阴历实际上都是阴阳历，例如全世界所有华人及朝鲜、韩国和越南及明治维新前的日本都是使用的夏历。

阴阳历（英语：lunisolar calendar），在天文学中是指兼顾月相周期和太阳周年运动所安排的历法。一年有12个朔望月，过若干年（一般为十九岁一章）安置一个闰月，使年的平均值大约与回归年相当。夏历就是阴阳历的一种，具体的历法还包括纪年（纪元）的方法。中国、日本、朝鲜、及中东以色列的传统历法也是阴阳历，其他民族如藏族、傣族也是使用阴阳历。

农历又称夏历，是现今依旧广泛使用的中国传统历法，在古代一般称“黄历”或“皇历”，近代以来又称为夏历、阴历、旧历等。事实上，夏历不是阴历，而是阴阳历；夏历不是农历，阳历才是真正的农历；夏历不是旧历，而是现今依然广泛使用的历法，因此很多人主张为夏历正名。

在农业气象学中，阴历略微不同于农历、殷历、古历、旧历，是指中国传统上使用的夏历。而在天文学中认为夏历实际上是一种阴阳历。在古代农业经济中，春天播种、秋天收耕，本来阳历应更能反映农业周期，但不少古代历法都是由月亮算起，一个推测是黑夜中的月亮特别容易观察，月亮盈亏一目了然，直至天文技术成熟后，他们才能观察到太阳在历法中的作用。

\subsection{儒略历和阴历}
Julian calendar，儒略历，是格里历的前身，由罗马共和国独裁官儒略·恺撒采纳埃及亚历山大的希腊数学家兼天文学家索西琴尼计算的历法，在公元前45年1月1日起执行，取代旧罗马历法的一种历法。一年设12个月，大小月交替，四年一闰，平年365日，闰年于二月底增加一闰日，年平均长度为365.25日。由于累积误差随着时间越来越大，1582年后被教皇格里高利十三世改善，变为格里历，即沿用至今的西历。

现行公历即格里历，又译国瑞历、额我略历、格列高利历、格里高利历，是由意大利医生兼哲学家里利乌斯（Aloysius Lilius）改革儒略历制定的历法，由教皇格列高利十三世在1582年颁行。公历是阳历的一种，于1912年开始在中国正式采用，取代传统使用的中国历法农历，而中国传统历法是一种阴阳历，因而公历在中文中又称阳历、西历、新历。格里历与儒略历一样，格里历也是每四年在2月底置一闰日，但格里历特别规定，除非能被400整除，所有的世纪年（能被100整除）都不设闰日；如此，每四百年，格里历仅有97个闰年，比儒略历减少3个闰年。

格里历的历年平均长度为365.2425日，接近平均回归年的365.242199074日，即约每3300年误差一日，也更接近春分点回归年的365.24237日，即约每8000年误差一日；而儒略历的历年为365.25日，约每128年就误差一日。到1582年时，儒略历的春分日（3月21日）与地球公转到春分点的实际时间已相差10天。因此，格里历开始实行时，将儒略历1582年10月4日星期四的次日，为格里历1582年10月15日星期五，即有10天被删除，但原星期的周期保持不变。格里历的纪年沿用儒略历，自传统的耶稣诞生年开始，称为“公元”，亦称“西元”。

格里历1582年10月15日，合儒略历1582年10月5日，只有意大利、波兰、西班牙、葡萄牙开始用格里历，日期跳过10日。由于新历法是教皇颁布的，新教国家予以抵制。直到18世纪，大英帝国，包括英格兰、苏格兰、以及现在美国的一部份才采纳格里历，也就是儒略历 1752年 9月2日星期三的次日是格里历1752年9月14日星期四，日期跳过11日。值得注意的是，1582年，罗马教廷减去的是10天，而到1752年修改历法的时候却减去了11天的原因其实很简单，这涉及到了闰年的问题。

The proleptic Gregorian calendar is produced by extending the Gregorian calendar backward to dates preceding its official introduction in 1582.

\subsection{纪年}
纪年是人们给某一年起名的方法。主要的纪年有帝王纪年、公元纪年、岁星纪年和干支纪年等。
中国在汉武帝以前用帝王纪年，从即位年用元年、二年、三年……。改元时，用“中二年”“后元年”等。从汉武帝到清末，用年号纪年；1911年推翻帝制之后采用民国诞生时间来纪年，兼或使用公元纪年。1949年中华人民共和国成立以后采用全世界通用的公元纪年。干支纪年认为兴自东汉。东汉四分历以前，用岁星纪年和太岁纪年。到现在来用干支纪年。

西元，又称耶元、西历，一种源自于西方社会的纪年方法，以耶稣诞生年作为纪年的开始。在儒略历与格里高利历中，在耶稣诞生之后的日期，称为主后（拉丁语：Anno Domini，缩写为 A.D.），而在耶稣诞生之前，称为主前（英语：Before Christ，缩写为B.C.）。现代学者，为了淡化宗教色彩，多半改采用公元（Common era，缩写为C.E.）与公元前（Before the Common Era，缩写为 B.C.E.）的说法。

公历以耶稣的出生为参照。在6世纪时，东罗马帝国为了修订历法，以替代非常混乱的罗马历法，就请当时精通天文的僧侣建议一个更合理的纪年标准。由于自君士坦丁大帝以后，罗马帝国举国改信基督教，僧侣就决定改以耶稣出世的年份为新纪元一年。当时的僧侣就基于圣经上“耶稣被处决时约三十多岁”，就在耶稣处决那一年的年份减去三十，作为新纪元的元年。


\subsection{相关历史人物和事件}

盖乌斯·尤利乌斯·恺撒（拉丁文：Gaius Julius Caesar，前100年7月13日－前44年3月15日），罗马共和国末期的军事统帅、政治家，儒略家族成员。应该注意的是，中国大陆现在通常将此人译作尤利乌斯·凯撒，但在天文学上仍沿用“儒略历”一词，而不是“尤利乌斯历”。

郭守敬（1231年－1316年），字若思，邢台人，中国元朝的天文学家、数学家和水利学家。确定了一个月为29.530593日，一年为365.2425日。正式废除以前历法积累的时差，以实际观测为准。确定以一年的1/24作为一个节气，以没有中气的月份为闰月，此原则一直采用至今。

John Herschel proposed a correction to the Gregorian calendar, making years that are multiples of 4000 not leap years, thus reducing the average length of the calendar year from 365.2425 days to 365.24225. Although this is closer to the mean tropical year of 365.24219 days, his proposal has never been adopted because the Gregorian calendar is based on the mean time between vernal equinoxes (currently 365.2424 days).


前45年1月1日,恺撒起执行儒略历，取代旧罗马历法。
前44年，盖乌斯·尤利乌斯·恺撒遭到以布鲁图所领导的元老院成员暗杀身亡。
前32年，屋大维向安东尼宣战。奥古斯都，原名盖乌斯·屋大维·图里努斯（Gaius Octavius Thurinus），是罗马帝国的开国君主，统治罗马长达43年。
前23年，屋大维辞去执政官职，接受其他二职。一为保民官职（tribunicia potestas），二为“统治大权”。普遍认为奥古斯都在前23年里披上了黄袍。然而，他仍使用第一公民这个称号。
公元元年，王莽加爵“安汉公”。汉平帝追谥孔子为褒成宣尼公，封孔子后裔均为褒成侯，从此孔子正式登上中国传统社会的神坛。世界人口达2亿。
公元14年8月19日，奥古斯都逝世。罗马元老院决定将他列入“神”的行列，并且将8月称为“奥古斯都”月，这也是欧洲语言中8月的来源。














